package LeetCode.leetcode15;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {-2,0,1,1,2};
        threeSum(arr);

    }

    /**
     * 自己写的总是有点bug，应该在去重的地方
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        HashSet<List<Integer>> set = new HashSet<>();
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length < 3) {
            return lists;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int i;
        while (right - left >= 2) {
            for (i = left + 1; i < right; i++) {
                //如果这三个数都大于0
                if (nums[left] + nums[i] + nums[right] > 0) {
                    break;
                } else if (nums[left] + nums[i] + nums[right] == 0) {//如果找到这个数
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[i]);
                    list.add(nums[right]);
                    set.add(list);
                }
            }
            if (!(nums[left] + nums[i] + nums[right] > 0)){
                right--;
            }else {
                left++;
            }
            //如果第一个i都大于0，说明right大了，左移
//            if (nums[left] + nums[i] + nums[right] > 0) {
//                right--;
//            } else {//包括 i = right-1都小于0；和已经找到等于0的两种情况
//                left++;
//            }
//            if (right - left < 2) {
//                break;
//            }
        }
        lists.addAll(set);
        return lists;
    }

    /**
     * 正确题解
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        int sum;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    //添加元组
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return ans;
    }

}
